package SSF.App.DDoS;

import com.renesys.raceway.DML.*;
import com.renesys.raceway.SSF.*;
import java.util.*;

/** version 1.0.4 
 * <BR> SpoofFloodTracer: tracing spoofed ip packets flood with given 
 * destination address.
 */
public class SpoofFloodTracer
{
    //protected static final int RATIO = 0;
    //protected static final int ABSOLUTE_VALUE = 1;

    /* start checking this domain */
    public static final byte START_CHECK = (byte)0;

    /*this domain is suspicious and a fair amount of flood came from within it */
    public static final byte SUSPICIOUS = (byte)1;

    /* finished checking this domain */
    public static final byte END_CHECK = (byte)2;

    /* this domain doesn't have flow devices installed, and the automated tracing back ended here.*/
    public static final byte BROKEN = (byte)3;

    /** recorder used to record trace data for animation */
    protected StreamInterface Rec=null;

    /** record type of the trace back record */
    public static final String STREAM_TYPE = "TraceRec";

    /** file store trace data for animation */
    protected String traceOutputFile = null;

    /** simulated time cost of "processing" a single record */
    protected static final float PROCESS_RECORD_COST = (float)0.001;

    /** debug switch */
    protected boolean DEBUG=false;

    /** stream ID */
    protected String streamID;

    /** storing topology information */
    protected NetMap netMap=null;

    /** doing cross-domain DDoS tracing */
    protected CD_DDoSTracer cTracer=null;

    /** the target ip of the spoofed flood */
    protected int targetIP=0;

    /** the start time of relevant flows */
    protected float startTime = 0;

    /** the end time of relevant flows.*/
    protected float endTime = Float.MAX_VALUE;

    /** the threashhold of the ratio, default 25% */
    protected float ratio_t = (float)0.25;

    /** the threashold of the absolute number of flows, default 80 */
    protected long nFlows_t = 80;
    /** the starting "domain" nhi prefix */
    protected String curNhiPrefix = null;

    /** the flow data file name prefix */
    protected String flowFilePrefix = null;

    /** the map data file name */
    protected String mapFile = null;

    /** the simulated time cost by now */
    protected float curTime = (float)5.0;

    /** the first "level" levels of nhi prefix is considered as domain ID.
     * default = 1*/
    protected int level = 1;

    /** data structure used for BFS search */
    protected LinkedList domainQueue;

    protected LinkedList recordList;

    /** used when computing the simulated time cost */
    protected long oldRecCount = 0;

    /** Dumb constructor that does nothing.*/
    public SpoofFloodTracer()
    {
    }

    /** report the value of all the status variables*/
    public void reportStatus()
    {
	System.out.println("-----== Spoof Flood Tracer status ==------"
			   +"\ntargetIP:\t"+ IP_s.IPtoString(targetIP)
			   +"\nratio threshold:\t"+ratio_t
			   +"\nflows threshold:\t"+nFlows_t
			   +"\ncurrent NHI domain:\t"+ curNhiPrefix
			   +"\nflow data file prefix:\t"+flowFilePrefix
			   +"\nmap file:\t"+mapFile
			   +"\ntraceOutputFile:\t"+traceOutputFile
			   +"\ntime cost (fake):\t"+curTime);
    }


    /** 
     * Read topology data in for the future query. 
     * @ret 0 if succeed, -1 otherwise
     */
    public int createMap()
    {
	netMap = new NetMap(streamID);
	//FIX ME, more operations need to actually read data in.
	try {
	    netMap.connectRead(mapFile);
	    netMap.disconnect();
	} catch (streamException se) {
	    System.err.println(se.getMessage());
	    System.err.println("Failed to collect map data for tracing.");
	    return -1;
	}
	return 0;
    }

    public void setTraceOutputFile(String fname)
    {
	traceOutputFile = fname;
    }
    public void setStreamID(String streamID)
    {
	this.streamID = streamID;
    }

    public void setTarget(int ip, String domainNhiPrefix)
    {
	targetIP = ip;
	curNhiPrefix = domainNhiPrefix;
    }

    public void setRatio(float rate)
    {
	if (rate > 1 || rate < 0) {
	    System.err.println("Invalid ratio for SpoofFloodTracer:"+ rate);
	    return;
	}
	ratio_t = rate;
    }

    public void setNumFlows(long nFlows)
    {
	if (nFlows < 0) {
	    System.err.println("Invalid flows threashold for SpoofFloodTracer:"
			       + nFlows);
	    return;
	}
	nFlows_t = nFlows;
    }

    /** configur the tracer with DML configuration */
    public void config(Configuration cfg) throws configException
    {
	String evals=null;

	evals = (String)cfg.findSingle("debug");
	if (evals != null)
	    if (evals.equals("true"))
		DEBUG = true;

	evals = (String)cfg.findSingle("streamID");
	if (evals == null)
	    throw new configException("tracer attribute missing: streamID.");
	else streamID = evals;

	evals = (String)cfg.findSingle("flow_file_prefix");
	if (evals == null)
	    throw new configException("tracer attribute missing: flow_file_prefix");
	else flowFilePrefix = evals;
	
	evals = (String)cfg.findSingle("map_file");
	if (evals == null)
	    throw new configException("tracer attribute missing: map_file");
	else mapFile = evals;

	evals = (String)cfg.findSingle("trace_output_file");
	if (evals != null)
	    traceOutputFile = evals;

	//read in topology data
	if (-1 == createMap())
	    throw new configException("tracer failed to read in topolgy information from the map file:" + mapFile);

	try {
	    evals = (String)cfg.findSingle("domain_nhi_level");
	    if (evals != null) {
		level = Integer.valueOf(evals).intValue();
	    }

	    evals = (String)cfg.findSingle("start_time");
	    if (evals != null)
		startTime =Float.valueOf(evals).floatValue();

	    evals = (String)cfg.findSingle("end_time");
	    if (evals != null)
		endTime = Float.valueOf(evals).floatValue();

	    //attribute about the threshold
	    evals = (String)cfg.findSingle("ratio_threshold");
	    if (evals != null)
		ratio_t = Float.valueOf(evals).floatValue();
	    
	    evals = (String)cfg.findSingle("flows_threshold.");
	    if (evals != null) 
		nFlows_t = Integer.valueOf(evals).intValue();
	} catch (Exception any) {
	    throw new configException(any.getMessage());
	}

	//sepcify target either by ip or prefix
	evals = (String)cfg.findSingle("target_ip");
	if (evals == null) {
	    evals = (String)cfg.findSingle("target_nhi");
	    if (evals == null)
		throw new configException("tracer must has target_ip or target_nhi.");
	    else {
		targetIP = netMap.query(evals);
		curNhiPrefix = NHIDemuxer.getNhiPrefix(evals, level);
	    }
	} else {
	    targetIP = IP_s.StrToInt(evals);
	    //target_ip is given in ip, then it's nhi prefix must be given.
	    evals = (String)cfg.findSingle("start_nhi_prefix");
	    if (evals == null)
		throw new configException("target_ip given, but not start_nhi_prefix.");
	    else curNhiPrefix = evals;
	}

	reset();

	if (DEBUG) {
	    System.out.println("SpoofFloodTracer configuaration is done.");
	    reportStatus();
	}
    }

    /** reset the variables to the status before the tracing back, but not the time*/
    public void reset()
    {
	cTracer = new CD_DDoSTracer(streamID);
	domainQueue = new LinkedList();
	recordList = new LinkedList();
	// prepare the recorder for output.
	if (traceOutputFile != null) {
	    Rec = new BasicRecorder(streamID);
	}
    }

    /** trace back to the sources of the spoofed flood */
    public void traceback()
    {
	System.out.println("start tracing back...");

	DomainInfo dInfo;
	domainQueue.addLast(new DomainInfo(curNhiPrefix, curTime));
	cTracer.setQuery(targetIP, startTime, endTime);

	//do a BFS search
	dInfo = (DomainInfo)domainQueue.getFirst();
	while (dInfo != null) {
	    domainQueue.removeFirst();
	    domainTrace(dInfo);
	    if (domainQueue.size() == 0)
		break;
	    dInfo = (DomainInfo)domainQueue.getFirst();
	}
    }

    /** trace back in a given domain */
    protected void domainTrace(DomainInfo dInfo)
    {
	String curFileName = flowFilePrefix + "."+dInfo.nhiPrefix.replace(':','.');

	long egressFlowNum;
	long ingressFlowNum;
	long localFlowNum;
	
	//get the "starting time" for this domain.
	curTime = dInfo.time;
	curNhiPrefix = dInfo.nhiPrefix;

	//start checking this domain.
	record(curNhiPrefix, curTime, START_CHECK);

	//read flow information from the file
	cTracer.reset();
	try {
	    cTracer.connectRead(curFileName);
	} catch (streamException se) {
	    System.err.println(se.getMessage());
	    System.exit(-1);
	}

	//analyze the data and pull out those ones that are suspected

	egressFlowNum = cTracer.totalEgressFlows;
	ingressFlowNum = cTracer.totalIngressFlows;
	localFlowNum = egressFlowNum - ingressFlowNum;

	//update the time information according to the size of the flow records.
	curTime +=(cTracer.getRecordCount()-oldRecCount)* PROCESS_RECORD_COST ;
	oldRecCount = cTracer.getRecordCount();
	dInfo.time = curTime;

	//check whether the local subnet is responsible for a fair amount of the flood.
	if (isLocalSuspicious(localFlowNum, egressFlowNum)) {
	    gotDomain(localFlowNum, dInfo);
	    record(curNhiPrefix, curTime, SUSPICIOUS);
	} else
	    record(curNhiPrefix, curTime, END_CHECK);


	TraceInfo tInfo = null;

	//try to determin the next level of domains that need to be looked into.
	for (Enumeration enum = cTracer.ingressInfo();
	     enum.hasMoreElements();) {
	    tInfo = (TraceInfo)enum.nextElement();

	    if (suspiciousIngressPoint(tInfo,egressFlowNum))
		gotIngressPoint(tInfo);
	}
    }

    
    /**
     * check to see whether a given ingress point is responsible for a fair amount of the flood.
     * @ret true if it is, false other wise.
     */
    protected boolean suspiciousIngressPoint(TraceInfo tInfo, long egressFlow)
    {
	if (egressFlow == 0) {
	    if (tInfo.numFlow > nFlows_t)
		return true;
	    else return false;
	}

	if (tInfo.numFlow / egressFlow > ratio_t || tInfo.numFlow > nFlows_t)
	    return true;
	return false;
    }

    /** 
     * operations when got an suspected ingress point.
     */
    protected void gotIngressPoint(TraceInfo tInfo)
    {
	// get the peer nhi of this interface
	String peerNHI;
	int peerIP = netMap.getFirstPeerIP(tInfo.hostNHI+"("+tInfo.nicID+")");

	if (DEBUG)
	    System.out.println("Got suseciousIngressPoint:"+
			       tInfo.toString());
	   
	if (peerIP == -1) {
	    System.err.println("Error: no peer found for "+tInfo.hostNHI+"("+tInfo.nicID+")");
	    return;
	}
	peerNHI = netMap.query(peerIP);
	if (peerNHI == null) {
	    System.err.println("Error: no nhi for ip:"+IP_s.IPtoString(peerIP));
	    return;
	}

	//enqueue it so that it will be checked later on.
	domainQueue.addLast(new DomainInfo(NHIDemuxer.getNhiPrefix(peerNHI, level), curTime));
    }

    /** check wether the local domain is responsible for a faire amount of flood 
     * @ret true if it is.
     */
    protected boolean isLocalSuspicious(long localFlow, long egressFlow)
    {
	if (egressFlow == 0) //the domain where the target is
	    return false;
	return (localFlow / egressFlow > ratio_t || localFlow > nFlows_t);
    }

    /** operations when the local domain is suspicious */
    protected void gotDomain(long localFlow, DomainInfo dInfo) {
	if (DEBUG)
	    System.out.println("suspicious domain found:"+curNhiPrefix
			       +"\t numFlows:"+localFlow
			       +"\tsimulated time cost:"+curTime);
	//suspiciousDomainList.addLast(dInfo);
    }


    protected void summarize() {
	if (DEBUG)
	    System.out.println("----Spoof Flood Tracer Result-----");

	int streamTypeCode = -1;
	int sourceCode = -1;
	//try open record file.
	if (Rec != null) {
	    try {
		Rec.connectWrite(traceOutputFile);
		streamTypeCode = Rec.getRecordTypeCode(STREAM_TYPE);
		sourceCode = Rec.getRecordSourceCode("0");
	    } catch (streamException se) {
		System.err.println(se.getMessage());
		traceOutputFile = null;
		Rec = null;
		return;
	    }
	}

	//dump records to file in the reverse order
	if (recordList.size() == 0) {
	    System.err.println("no record for tracing back.");
	    return;   //no records.
	}

	byte[] curRec;
	float curTime;

	//hardcoded. FIX ME!!!!!!!!, tempararily for the "lost 1st record bug"
	//in the animation 
	if (recordList.size() > 0) {
	    curRec = (byte[])recordList.getLast();
	    curTime = BytesUtil.bytesToFloat(curRec, 0);
	    Rec.send(streamTypeCode, sourceCode, 0.0, curRec, 4, 
		     curRec.length-4);
	}
	

	while (recordList.size() > 0) {
	    curRec = (byte[])recordList.getLast();
	    curTime = BytesUtil.bytesToFloat(curRec, 0);

	    Rec.send(streamTypeCode,sourceCode,
		     curTime,
		     curRec,
		     4,                      //the first 4 bytes is the time
		     curRec.length-4);

	    if (DEBUG) {
		System.out.println("time cost:"+ curTime
				   +"\tdomain nhiPrefix:"+
				   BytesUtil.bytesToString(curRec, 4)
				   +"\tstatus:"+
				   ((curRec[curRec.length-1] == START_CHECK)?
				   "START_CHECK":
				   ((curRec[curRec.length-1] == END_CHECK)?
				    "END_CHECK":"SUSPICIOUS")));
	    }
	    recordList.removeLast();
	}

	Rec.disconnect();
	/*
	// dump the data to an Array.
        Object[] dResult = suspiciousDomainList.toArray();

	//sort the array according to the time cost
	Arrays.sort(dResult, (new DomainInfoComp()));

	//print out the result.
	for (int i=0; i<dResult.length; i++)
	    System.out.println("domain: "+dResult[i].toString());
	*/

	if (DEBUG)
	    System.out.println("----------------------------------");
    }

    protected void record(String nhiPrefix, float curTime, byte status)
    {
	//if (Rec == null) 
	//    return;       // no recorder device specified.

	// make a byte[] for further usage
	// nhiprefix + 1 + status + time
	byte[] bytes= new byte[nhiPrefix.length()+1+1+4];

	int index = BytesUtil.floatToBytes(curTime, bytes, 0);
	index = BytesUtil.stringToBytes(nhiPrefix, bytes, index);
	bytes[index] = status;

	byte[] curRec = null;
	//insert it in the RecordList with reverse time order
	for (ListIterator iter = recordList.listIterator();
	     iter.hasNext();) {
	    curRec = (byte[])iter.next();
	    if (BytesUtil.bytesToFloat(curRec, 0) <= curTime)
		break;
	}

	if (curRec == null)
	    recordList.add(bytes);
	else recordList.add(recordList.indexOf(curRec), bytes);
    }

    public static String recordToString(byte[] bytes, int offset, int length)
    {
	return ("domain nhiPrefix:"+
		BytesUtil.bytesToString(bytes, offset)
		+"\tstatus:"+
		((bytes[offset+length-1] == START_CHECK)?
		 "START_CHECK":
		 ((bytes[offset+length-1] == END_CHECK)?
		  "END_CHECK":"SUSPICIOUS")));
    }
    public static void main(String[] argv)
    {
	if (argv.length < 1) {
	    System.err.println("Usage: java SpoofFloodTracer <tracer config file>");
	    return;
	}

	dmlConfig tracerConfig = null;

	tracerConfig = new dmlConfig(argv[0]);
	
	Configuration tCfg = (Configuration)tracerConfig.findSingle(".spoof_flood_tracer");

	if (tCfg == null) {
	    System.err.println("Configuration must have a .SpoofFloodTracer attribute.");
	    System.err.println(tCfg);
	    System.exit(-1);
	}

	SpoofFloodTracer sfTracer = new SpoofFloodTracer();
	
	try {
	    sfTracer.config(tCfg);
	} catch (configException cfe) {
	    System.err.println(cfe.getMessage());
	    System.exit(-1);
	}

	if (sfTracer.DEBUG)
	    System.out.println("Complete configuring the tracer.");

	sfTracer.traceback();
	sfTracer.summarize();
	return;
    }

    class DomainInfo
    {
	String nhiPrefix;
	float time;
	//byte status;

	DomainInfo(String nhiPrefix, float time)
	{
	    this.nhiPrefix = nhiPrefix;
	    this.time = time;
	    //status = UNKNOWN;
	}

	/*void setStatus(byte status)
	{
	    this.status = status;
	}
	*/
	@Override
	public String toString()
	{
	    return ("nhiPrefix: "+nhiPrefix+"\ttime cost: "+time);
	    //return ("nhiPrefix: "+nhiPrefix+"\ttime:"+time + "status:"+
	    //    (status==SUSPICIOUS?"SUSPICIOUS":(status == BROKEN?"BROKEN":"UNKNOWN")));
	}
    }

    class DomainInfoComp implements Comparator
    {
	@Override
	public int compare(Object o1, Object o2)
	{
	    float t =  ((DomainInfo)o1).time - ((DomainInfo)o2).time;
	    if (t>0)
		return 1;
	    else if (t<0)
		return -1;
	    else return 0;
	}

	@Override
	public boolean equals(Object obj)
	{
	    return super.equals(obj);
	}
    }
}
